package com.hans.scala.GenericTypesAndMethods

abstract class Stack[A] {
  def push(x: A): Stack[A] = new NonEmptyStack[A](x, this)

  def isEmpty: Boolean

  def top: A

  def pop: Stack[A]
}

class EmptyStack[A] extends Stack[A] {
  def isEmpty = true

  def top = error("EmptyStack.top")

  def pop = error("EmptyStack.pop")
}

class NonEmptyStack[A](elem: A, rest: Stack[A]) extends Stack[A] {
  def isEmpty = false

  def top = elem

  def pop = rest
}

object Example {
  def isPrefix[A >: Null](p: Stack[A], s: Stack[A]): Boolean = {
    p.isEmpty ||
      p.top == s.top && isPrefix[A](p.pop, s.pop)
  }

  def main(args: Array[String]) {
//    val x = new EmptyStack[Int]
//    val y = x.push(1).push(2) // t1 = (1,x)  t2 = (2,t1)  y=t2   y.pop=t2.pop=t1
//    println(y.pop.top)
//    println(y.pop.pop.top)  //java.lang.RuntimeException: EmptyStack.top

    val s1 = new EmptyStack[String].push("abc")     //e1 s1=(abc,e1)
    val s2 = new EmptyStack[String].push("abx").push(s1.top) //e2 t=(abx,e2) s2=(abc,t)
    println(isPrefix[String](s1, s2))
//
  }
}
